

namespace ZIFUCHUAN{

/**
 * @brief 最小表示，参数表示 [begin, begin+n)的区域
 * @param begin 
 * @param n 
 * @return 返回距离begin的偏移量
 */
template<typename IT>
int minRepresentation(IT begin, int n){
    int i = 0, j = 1, k = 0;
    while(i < n && j < n && k < n){
        while(k < n && *(begin + (i + k) % n) == *(begin + (j + k) % n)) ++k;
		if(k == n) break;
		
		if(*(begin + (i + k) % n) < *(begin + (j + k) % n)) j += k + 1;
		else i += k + 1;
		if(i == j) ++i;
		k = 0;
	}
    return min(i, j);
}

}

